package com.leo.leetcode.s100;

import java.util.Arrays;

/**
 *
 * @author xuexiaolei
 * @version 2017年12月01日
 */
public class T88MergeSortedArray {
    /**
     * 先将nums1都移动到后n位
     *      傻了！！直接先排大序不就行了！！
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) return;
        //将nums1统一往后退n个
        for (int i = m-1; i >= 0; i--) {
            nums1[i+n] = nums1[i];
        }
        int i1 = n;//nums1的起始位置
        int i2 = 0;//nums2的起始位置
        for (int i = 0; i < m + n; i++) {
            if (i1 == m+n) {
                for (int j = i; j < m + n; j++) {
                    nums1[j] = nums2[i2];
                    i2++;
                }
                return;
            }
            if (i2 == n) return;
            if (nums1[i1] < nums2[i2]){
                nums1[i] = nums1[i1];
                i1++;
            }else {
                nums1[i] = nums2[i2];
                i2++;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums1 = new int[]{4,5,6,0,0,0,0};
        merge(nums1,3,new int[]{1,2}, 2);
        System.out.println(Arrays.toString(nums1));

        nums1 = new int[]{4,5,6,0,0,0,0};
        merge(nums1,3,new int[]{}, 0);
        System.out.println(Arrays.toString(nums1));

        nums1 = new int[]{4,5,6,0,0,0,0};
        merge(nums1,3,new int[]{7,8}, 2);
        System.out.println(Arrays.toString(nums1));

        nums1 = new int[]{4,5,6,9,0,0,0};
        merge(nums1,4,new int[]{1,2,7}, 3);
        System.out.println(Arrays.toString(nums1));
    }
}
